
local function _find_smallest(array)
    local smallest = array[1]
    local index = 1
    for i=2, #array do
        if array[i] < smallest then
            smallest = array[i]
            index = i
        end
    end
    return index
end

-- the return array is in a ascending order
local function _selection_sort(array)
    local ret = {}
    local i
    local n = #array
    for _=1, n do
        i = _find_smallest(array)
        ret[#ret+1] = table.remove(array, i)
    end
    return ret
end

local function test()
    local arr = {0, -100, 1000, 1, 5}
    local n = #arr
    local ret = _selection_sort(arr)

    local i = 1
    while i < n do
        if ret[i] > ret[i+1] then
            break
        end
        i = i + 1
    end
    assert(i == n)
end

test()

